home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / ingres04.lzh / source / iutil / btree_util.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-05-30  |  8.3 KB  |  403 lines
  1. #include    <btree.h>
  2. #include    <ingres.h>
  3. #include    <opsys.h>
  4. #include    <sccs.h>
  5.  
  6. SCCSID(@(#)btree_util.c    8.3    5/30/88)
  7.  
  8. /*    Trace up to the root of the BTree, incrementing (or decrementing) all
  9. **    key values.
  10. **
  11. **    Parameters :
  12. **        tree - BTree filename (I)
  13. **        block - starting node from which path is traced (I)
  14. **        inc - either +1 or -1 (I)
  15. */
  16.  
  17. tracepath(rootpage, block, inc)
  18.  
  19. long rootpage;
  20. register struct locator *block;
  21. register int inc;
  22. {
  23.     struct locator     p, child;
  24.  
  25.     if (block->pageno != rootpage)    /* if at root, no need for adjustment */
  26.     {
  27.         bmove(block, &child, sizeof(struct locator));
  28.  
  29.         /* trace up to root node */
  30.         do
  31.         {
  32.             p.pageno = child.page.parent;
  33.             parentkey(child.pageno, &p);
  34.             p.page.node.intnode.key[p.offset] += inc;
  35.             write_node(p.pageno, &p.page);
  36.             bmove(&p, &child, sizeof(struct locator));
  37.         } while (p.pageno != rootpage);
  38.     }
  39. }
  40.  
  41. /*    Determines which key/ptr pair is the parent of the given page
  42. **
  43. **    Parameters :
  44. **        tree - BTree filename (I)
  45. **        block - page number of child (I)
  46. **        prt - information about the parent of the child (I, O)
  47. **
  48. */
  49.  
  50. parentkey(block, prt)
  51.  
  52. long block;
  53. register struct locator *prt;
  54. {
  55.     register int    i;
  56.  
  57.     get_node(prt->pageno, &prt->page);
  58.     /* find pointer in parent which references desired block */
  59.     for (i = 0; prt->page.node.intnode.ptr[i] != block && i < prt->page.nelmts; ++i)
  60.         continue;
  61.  
  62.     if (i == prt->page.nelmts)
  63.         syserr("parentkey: child = %ld", block);
  64.     prt->offset = i;
  65.     return(0);
  66. }
  67.  
  68. /*    Retrieve a node from the BTree
  69. **
  70. **    Parameters :
  71. **        tree - BTree filename (I)
  72. **        pagenum - page number of page to be retrieved (I)
  73. **        buffer - buffer into which page is retrieved (O)
  74. */
  75.  
  76. get_node(pagenum, buffer)
  77.  
  78. long pagenum;
  79. register struct BTreeNode *buffer;
  80. {
  81.     extern int    Btree_fd;
  82.  
  83.     if ( lseek(Btree_fd, pagenum * PGSIZE, 0) == -1 )
  84.         syserr("GET_NODE: seek to %ld failed",pagenum);
  85.     if (read(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
  86.         syserr("GET_NODE: read btree, page %ld", pagenum);
  87. }
  88.  
  89. /*    Write a node into the BTree file name 
  90. **
  91. **    Parameters :
  92. **        tree - BTree filename (I)
  93. **        pagenum - page number of page to be written (I)
  94. **        buffer - buffer containing page to be written (I)
  95. */
  96.  
  97. write_node(pagenum, buffer)
  98.  
  99. long pagenum;
  100. register struct BTreeNode *buffer;
  101. {
  102.     extern int    Btree_fd;
  103.  
  104.     lseek(Btree_fd, pagenum * PGSIZE, 0);
  105.     if (write(Btree_fd, buffer, PGSIZE) != PGSIZE)
  106.         syserr("WRITE_NODE: write btree, page %ld", pagenum);
  107. }
  108.  
  109. /*    Retrieves a new page from the BTree file.  If there is an empty page
  110. **    in the file, that page is used.  Otherwise, a new page is added to
  111. **    the end of the file.
  112. **
  113. **    Parameters :
  114. **        tree - BTree filename (I)
  115. **
  116. **    Returns :
  117. **        page number of new page
  118. */
  119.  
  120. long
  121. new_page(tree)
  122.  
  123. char *tree;
  124. {
  125.     int             i;
  126.     long            freepage, newpage;
  127.     struct BTreeNode     page, root, garbage;
  128.     struct stat        fileinfo;
  129.     extern DESC        Btreesec;
  130.  
  131.     get_node(RT, &root);
  132.     freepage = root.parent;
  133.     if (freepage == 0)
  134.     /* no free pages in file, add a new page to the end */
  135.     {
  136.         /* determine page number of page at very end of file */
  137.         stat(tree, &fileinfo);
  138.         newpage = fileinfo.st_size / PGSIZE;
  139.         write_node(newpage, &page);
  140.     }
  141.     else
  142.     /* use first free page, adjusting free page chain */
  143.     {
  144.         newpage = freepage;
  145.         get_node(newpage, &garbage);
  146.         root.parent = garbage.parent;
  147.         write_node(RT, &root);
  148.     }
  149.     return(newpage);
  150. }
  151.  
  152. /*    Returns an empty file to the empty file list.  The head of the list
  153. **    is indicated through the parent of the root and linked together
  154. **    through the parents of the empty pages.
  155. **
  156. **    Parameters :
  157. **        tree - BTree filename (I)
  158. **        pagenum - page number of empty page (I)
  159. */
  160.  
  161. return_page(pagenum)
  162.  
  163. long pagenum;
  164. {
  165.     struct BTreeNode    root, freepage;    
  166.  
  167.     /* indicate that page is free by inserting its page number at the
  168.     ** head of the free page list */
  169.     get_node(RT, &root);
  170.     get_node(pagenum, &freepage);
  171.     freepage.parent = root.parent;
  172.     freepage.depth = 0;
  173.     write_node(pagenum, &freepage);
  174.     root.parent = pagenum;
  175.     write_node(RT, &root);
  176. }
  177.  
  178. /*
  179. **    Determine the lid that corresponds to a given position in the B-Tree.
  180. **
  181. **    Parameters :
  182. **        tree - BTree name (I)
  183. **        tidloc - location in BTree (I)
  184. **
  185. **    Returns :
  186. **        lid value
  187. */
  188. get_lid(tidloc, lid)
  189.  
  190. TID *tidloc;
  191. long lid[];
  192. {
  193.     static struct locator    tid;
  194.     register int        i, j;
  195.     long            l, child;
  196.  
  197.     do
  198.     {
  199.         /* determine where in BTree to search */
  200.         pluck_page(tidloc, &tid.pageno);
  201.     
  202.         get_node(tid.pageno, (char *) &tid.page);
  203.         tid.offset = tid.page.node.leafnode.back_ptr[tidloc->line_id & I1MASK];
  204.  
  205.         if (tid.offset > tid.page.nelmts - 1)
  206.             syserr("get_lid: bad tid location %ld, tid.offset=%d, tid.page.nelmts=%d", *tidloc, tid.offset,tid.page.nelmts);
  207.     
  208.         /* scan through leaf */
  209.         for (l = 1, i = tid.offset; i > 0; ++l, --i)
  210.             continue;
  211.         /* trace up to root, adding keys */
  212.         while (!tid.page.depth)
  213.         {
  214.             child = tid.pageno;
  215.             tid.pageno = tid.page.parent;
  216.             parentkey(child, &tid);
  217.             for (i = tid.offset - 1; i >= 0; l += tid.page.node.intnode.key[i--])
  218.                 continue;
  219.         }
  220.         lid[tid.page.depth - 1] = l;
  221. #        ifdef xATR1
  222.             if (tTf(24,0))
  223.                 printf("lid=%ld\n", lid[tid.page.depth - 1]);
  224. #        endif
  225.         bmove(&tid.page.prttree, tidloc, LIDSIZE);
  226.     } while (tid.page.depth > 1);
  227. }
  228.  
  229. /*
  230. **    Uses the secondary btree relation to find the btree tid corresponding 
  231. **    to a given main relation tid
  232. */
  233.  
  234. search_btree(mtid, tidloc)
  235.  
  236. TID mtid; 
  237. register TID *tidloc;
  238. {
  239.     char        key[2 * LIDSIZE], tup[2 * LIDSIZE];
  240.     TID        tid;
  241.     extern DESC    Btreesec;
  242.  
  243. #    ifdef xATR1
  244.         if (tTf(24,0))
  245.         {
  246.             printf("In Search_btree: searching for tid %ld\n", mtid);
  247.             printdesc(&Btreesec);
  248.         }
  249. #    endif
  250.     clearkeys(&Btreesec);
  251.     setkey(&Btreesec, key, &mtid, 1);
  252.     if (!getequal(&Btreesec, key, tup, &tid))
  253.         bmove(tup + LIDSIZE, tidloc, LIDSIZE);
  254.     else
  255.         syserr("search_btree:can't find mtid %ld in btree", mtid);
  256. #    ifdef xATR1
  257.         if (tTf(24,0))
  258.             printup(&Btreesec, tup);
  259. #    endif
  260. }
  261.  
  262. /*
  263. **    Linearly searches the leaves of the BTree for a desired tid
  264. **
  265. **    Parameters :
  266. **        tree - BTree file name (I)
  267. **        tid - desired tid value (I)
  268. **        tidloc - location of the desired tid (O)
  269. */
  270.  
  271. lin_search(level, tid, tidloc, lid, tupcnt)
  272.  
  273. int level;
  274. long tid;
  275. TID *tidloc;
  276. long lid[];
  277. long tupcnt;
  278. {
  279.     struct locator    block;
  280.     register int    i;
  281.     long        page, t, next;
  282.     int        found;
  283.     long        nextpage, count;
  284.     int        forward, first;
  285.  
  286.     page = RT;
  287.     for (i = 0; i < level - 1; ++i)
  288.     {
  289.         t = get_tid(page, lid[i], &block);
  290.         page = t;
  291.     }
  292.  
  293.     found = 0;
  294.     forward  = 0;
  295.     first = 1;
  296.     do
  297.     {
  298.         if (!forward)
  299.         {
  300.             get_node(page, &block.page);
  301.             next = block.page.nexttree;
  302.         }
  303.         count = 0;
  304.  
  305.         /* start at leftmost leaf */
  306.         do
  307.         {
  308.             get_node(page, &block.page);
  309.             if (forward)
  310.                 nextpage = block.page.nexttree;
  311.             else
  312.                 nextpage = block.page.prevtree;
  313.             get_tid(page, 1, &block);
  314.             for ( ; ; )
  315.             {
  316.                 /* search through leaf */
  317.                 for (i = 0; i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] != tid; ++i)
  318.                 {
  319.                     if (!first)
  320.                         ++count;
  321.                 }
  322.                 if (i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] == tid)
  323.                 {
  324.                     found = 1;
  325.                     break;    /* tid found */
  326.                 }
  327.                 first = 0;
  328.                 if (!(block.pageno = block.page.node.leafnode.nextleaf) || count >= tupcnt)
  329.                     break;    /* all leaves exhausted */
  330.                 else
  331.                     /* try leaf to the right */
  332.                     get_node(block.pageno, &block.page);
  333.             }
  334.             if (found || count >= tupcnt)
  335.                 break;
  336.         } while (page = nextpage);
  337.         nextpage = next;
  338.         forward = !forward;
  339.     } while (forward != 0 && !found);
  340.     if (!found)
  341.         syserr("search_btree: tid not found %ld", tid);
  342.     else
  343.     {
  344.         stuff_page(tidloc, &block.pageno);
  345.         tidloc->line_id = block.page.node.leafnode.tid_loc[i];
  346.     }
  347. }
  348.  
  349. /*
  350. **    Determines the value corresponding to the very last lid in the
  351. **    BTree.
  352. **
  353. **    Parameters :
  354. **        tree - BTree file name (I)
  355. **
  356. **    Returns :
  357. **        value of last lid
  358. */
  359. long
  360. last_lid(rootpage)
  361.  
  362. long rootpage;
  363.  
  364. {
  365.     register int         i;
  366.     long            lid;
  367.     struct BTreeNode    root;
  368.  
  369.     lid = 0;
  370.     get_node(rootpage, &root);
  371.     if (root.nodetype == 'L')
  372.         lid = root.nelmts;
  373.     else
  374.         for (i = 0; i < root.nelmts; ++i)
  375.             lid += root.node.intnode.key[i];
  376.     ++lid;
  377.     return(lid);
  378. }
  379.  
  380. /*
  381. **    Changes the tid value stored in the leaf of a BTree node
  382. **
  383. **    Parameters :
  384. **        tree - BTree file name (I)
  385. **        tid - new tid value (I)
  386. **        tidloc - location of tid to be replaced (I)
  387. */
  388.  
  389. replace_btree(tid, tidloc)
  390.  
  391. long tid;
  392. register TID *tidloc;
  393.  
  394. {
  395.     long            pageno;
  396.     struct BTreeNode    p;
  397.  
  398.     pluck_page(tidloc, &pageno);
  399.     get_node(pageno, &p);
  400.     p.node.leafnode.tid_pos[tidloc->line_id] = tid;
  401.     write_node(pageno, &p);
  402. }
  403.